Many of the tasks that are addressed by decision-making systems and artificial intelligence can be represented as constraint satisfaction problems (CSPs). In this representation, the task is specified in terms of a set of variables, each of which can assume values in a given domain, and a set of constraints that the variables must simultaneously satisfy. The set of variables, domains and constraints is referred to as a CSP. Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. A solution to a CSP is an assignment of a value to all the variables from their respective domains that satisfies all of the constraints.
Constraint satisfaction methods have been found useful in a variety of applications, including:                Artificial intelligence        Robotic control        Temporal reasoning        Natural language processing        Spatial reasoning        Test-case generation for software and hardware systems        Machine vision        Medical diagnosis        Resource allocation        Crew scheduling        Time tabling        Frequency allocation        Graph coloring.        
For example, Bin et al. describe a constraint satisfaction method for use in automated generation of test programs, in a paper entitled “Using a Constraint Satisfaction Formulation and Solution Techniques for Random Test Program Generation,” IBM Systems Journal 41:3 (2002), pages 386-402. The authors show how random test program generation can be modeled as a CSP, and they describe a set of solution techniques that are used in practical test-case generation tools. Adir et al. describe a test generator that uses a dedicated CSP solver in a paper entitled “Piparazzi: A Test Program Generator for Micro-architecture Flow Verification,” Eighth IEEE International High-Level Design Validation and Test Workshop (Nov. 12-14, 2003), pages 23-28. The test generator converts user requests for micro-architectural events into test programs. Further aspects of the use of CSP solving in automatic test-case generation are described in U.S. Patent Application Publication 2002/0169587 A1.
The network of constraints in a CSP can be viewed as a hypergraph, having a node for each variable and a hyper-edge for each constraint. These hyper-edges are referred to as arcs, wherein the members of such an arc are the variables that appear in the constraint to which the arc corresponds. An arc is said to be consistent if for any variable of the arc, and any value in the domain of the variable, there is a valid assignment of values to the other variables on the arc that satisfies the constraint represented by the arc. If every arc in the hypergraph is consistent, then the network is said to be arc-consistent.
One family of solution for CSPs are algorithms based on maintaining arc consistency. These algorithms were introduced by Mackworth in an article entitled “Consistency in Networks of Relations,” published in Artificial Intelligence 8, pages 99-118 (1977). Arc consistency algorithms are based on the observation that given variables v1, and v2, with discrete domains D1 and D2, if xεD1, and there is no yεD2 that satisfies a given constraint Pij imposed on v1, and v2, then x can be deleted from D1. This basic action of arc consistency algorithms is embodied in the Boolean procedure “REVISE,” as defined by Mackworth in the above-mentioned paper. The arcs of the CSP network are maintained in a queue (Q), and REVISE is applied to the arcs in the queue until a solution is found.
The concept of a CSP was generalized by Mittal et al. to cover more complex problems, in which variables may be active or inactive, in a paper entitled “Dynamic Constraint Satisfaction Problems,” Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90) (Boston, Mass., July 1990), pages 25-32. This generalization is commonly referred to as “Conditional CSP,” or CondCSP. A CondCSP comprises the following:                A set of variables V={v1, v2, . . . , vn}.        A set of domains D={D1, D2, . . . , Dn}, such that Di is the set of valid values for the variable vi.        A set of initial variables VI⊂V, VI≠φ.        A set of compatibility constraints Ccomp.        A set of activity constraints Cact.        
In contrast to the traditional definition of CSP, a variable in a CondCSP can be either active or inactive. A variable is assigned a value only if it is active. A compatibility constraint specifies the set of allowed combinations of values for a set of variables. A compatibility constraint is active only if all its variables are active. An activity constraint has the form
in which C is defined in the same manner as a compatibility constraint, and v is a variable. Such an activity constraint states that if the left hand constraint C holds, then the variable v is active. Activity constraints may also take the form
(wherein rn stands for “require not”), which states that the variable v is not active if constraint C holds. A solution to a CondCSP contains (a) a set of active variables and (b) a value assignment to all the active variables, in which each variable is assigned a value from its domain, the assignment satisfying all the active compatibility constraints. The assignment and the set of active variables must satisfy all the activity constraints. A solution is considered to be minimal if no proper subset of the assignment is itself a solution.
Sabin et al. suggested a method for applying arc-consistency techniques to CondCSPs, in “Greater Efficiency for Conditional Constraint Satisfaction,” Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003) (Kinsale, County Cork, Ireland, 2003). For this purpose, the CondCSP is reformulated as a standard CSP, by adding null values to the variable domains and transforming CondCSP constraints into CSP constraints. Another technique for reducing a CondCSP to a conventional CSP is described by Gelle et al. in “Solving Mixed and Conditional Constraint Satisfaction Problems,” Constraints Journal 8:2 (2003), pages 107-141.